Masala #0418

Azimjon $N$ sonidan ildizi $N$ ga teng bo’lgan sikil mavjud bo’lmagan daraxt hosil qilishni ajoyib yo’lini o’ylab topdi, ya’ni u daraxni quyidagicha hosil qiladi.

• $N$ sonining tub bo’luvchilari ichidan eng kichigini tanlab oladi ya’ni $P_i$ ni;
• $N/P_i$ va $P_i$ sonlarini $N$ ga ulaydi;
• $N$ ning yangi qiymati uchun $N=N/P_i$ ni oladi.

Bu jarayondi N soni tub son bo’lib qolguncha davom ettiradi. Sizning vazifangiz hosil bo’lgan daraxtning ildizidan tub qiymatli shoxlarining uchigacha bo’lgan masofalar yig’indisini hisoblash(ikki bog’langan tugunlarni o’rtasidagi masofa 1 ga teng deb hisoblang).

Misol: $N=8$ bo’lgan holat rasimda tasvirlangan.

Kirish fayilida yagona natural son $N(2 \le N \le 10^{12})$.

Сhiqish fayilida yagona son masalaning javobi.